Three-dimensional (“3D”) digital data may be produced by a variety of devices that involve three-dimensional scanning or sampling and/or numerical modeling. For example, computed tomography (CT) and magnetic resonance imaging (MRI) devices scan portions of the human body and generate image slices of the body, which when combined or stacked, generate a 3D representation of the body, including its surface and internal volume.
Volume graphics represent a promising way to achieve the degree of realism required for high quality 3D simulations and visualization applications because volume models can contain all the surface and internal characteristics of a real object. This is in contrast to, for example, polygon-based graphics, which contain only the information about the surfaces of a 3D object. In the case of volume graphics, volume elements (i.e., “voxels”) are the base data used to represent 3D objects. Typically, voxels are simply pixels that have a third coordinate z in addition to x and y coordinates in a Cartesian coordinate system (though voxels may also take various other forms). In other words, voxels are equally sized cubes that form a discretely defined 3D space. A typical voxel-based 3D scene can consist of one or more “voxel sets”, each of which in turn consists of one or more voxels. For example, the 3D scene may include one or more sets of MRI slices, each forming a voxel set, which in turn includes a plurality of voxels within each voxel set. 3D voxel data are rendered to produce a 2D image on a suitable output device, such as a video display or a printer. As used herein, the term “render” means to produce a 2D graphics image on an output device from a 3D voxel data file.
NGRAIN® graphics technology, embodied in various software available from NGRAIN Corp. of Vancouver B.C., Canada, offers a volume-graphic based 3D visualization platform to build real time interactive 3D applications. Briefly, NGRAIN® technology permits 3D modeling of an object, wherein each of multiple parts or layers forming the object can be represented as a voxel set each consisting of one or more voxels. Thus, according to NGRAIN® technology, it is possible to manipulate each part or layer independently from each other or from the object as a whole, in 3D space, such as to create an exploded view of the object to show the details of its parts, or to peel off an outer layer of the object to reveal its inner layer. Since the voxel data structure used in NGRAIN® technology permits each voxel to be associated with an unlimited number of attributes (color, texture, normal, weight, density, etc.), these attributes can be used to give a rendered image a highly realistic look. Further, the voxel data structure and routines used to construct, manipulate, and render voxel data are such that specialized graphics hardware is not required—NGRAIN® technology can run on any conventional personal computer, including a laptop.
Various details of NGRAIN® technology are described in commonly owned Patent Cooperation Treaty Publication No. WO 02/07088 A2 entitled “LIGHTING ADJUSTMENT METHODS AND APPARATUS FOR VOXEL DATA,” commonly owned Patent Cooperation Treaty Publication No. WO 02/07089 A2 entitled “APPARATUS AND METHOD FOR ASSOCIATING VOXEL INFORMATION WITH DISPLAY POSITIONS,” commonly owned U.S. Pat. No. 6,867,774 B1 entitled “METHOD AND APPARATUS FOR TRANSFORMING POLYGON DATA TO VOXEL DATA FOR GENERAL PURPOSE APPLICATIONS,” commonly owned U.S. Pat. No. 7,050,054 B2 entitled “METHOD, APPARATUS, SIGNALS AND CODES FOR ESTABLISHING AND USING A DATA STRUCTURE FOR STORING VOXEL INFORMATION,” commonly owned U.S. Pat. No. 7,218,323 B1 entitled “METHOD AND SYSTEM FOR RENDERING VOXEL DATA WHILE ADDRESSING MULTIPLE VOXEL SET INTERPENETRATION,” commonly owned U.S. patent application Ser. No. 10/309,411 entitled “METHOD AND APPARATUS FOR TRANSFORMING POINT CLOUD DATA TO VOLUMETRIC DATA,” and commonly owned U.S. patent application Ser. No. 11/396,373 entitled “METHOD AND SYSTEM FOR ORGANIZING AND RENDERING MULTIPLE GEOMETRIC PARTS WITHIN A VOLUME GRAPHICS DATA SET,” which are all specifically incorporated herein by reference. Additional details of NGRAIN® technology can also be found in an article, “Myths and Truths of Interactive Volume Graphics”, a paper that has been published in I/ITSEC 2004 Conference.
FIG. 1A illustrates an object 1 in the form of an airplane, which consists of eight parts (1 fuselage (1), 2 wings (2)(3), 2 engines (4)(5), 1 vertical stabilizer (6), and 2 horizontal stabilizers (7)(8)). Each part is represented by a voxel set including multiple voxels. For example, FIG. 1B shows a voxel set 2 that represents a horizontal stabilizer (7) of FIG. 1A, including multiple voxels arranged in x-y-z Cartesian coordinate system. Each voxel within the voxel set 2 is defined by its geometric location (x, y, z), in the Cartesian coordinate system. Each voxel is associated with a set of attributes, such as its shade information including color and alpha values, normal vector, texture, part/layer number (i.e., to which voxel set it belongs), etc. Voxels that are occupied by an object are termed occupied voxels 3, whereas voxels that are not occupied are termed empty voxels 4. Each voxel set may contain occupied voxels and/or empty voxels, and typically only occupied voxels are associated with attributes.
With the use of multiple parts (or multiple voxel sets) to render an object, there remains a risk of deadlocking during loading and rendering of these parts. Deadlocking is a situation where two or more processes (e.g., threads that may execute in parallel) wait for each other, and thus neither can proceed. For example, a load thread that loads 3D voxel data from a disk storage or a network onto a user computer (e.g., a personal computer) and a display thread that renders the loaded 3D voxel data on a display screen of the user computer may deadlock, halting the entire operation.